public class LeetCode343 {
    public int integerBreak(int n) {
        // 特殊情况处理：当 n == 2 时，只能拆分为 1+1，所以返回 1。
        if (n == 2) {
            return 1;
        }

        // 初始化一个 dp 数组，长度为 n + 1，dp[i] 表示将 i 拆分后能得到的最大乘积。
        int[] dp = new int[n + 1];

        // 动态规划填表过程：
        for (int i = 2; i <= n; i++) { // 遍历每一个从 2 到 n 的值
            for (int j = 1; j < i; j++) { // 对于每个 i，尝试所有可能的拆分点 j
                // 更新 dp[i]，考虑两种情况：
                // 1. 直接使用 j * (i - j)，即不进一步拆分 i-j。
                // 2. 使用 j * dp[i - j]，即将 i-j 继续拆分以获得更大的乘积。
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[i - j] * j));
            }
        }

        // 返回 dp[n]，即为将 n 拆分后的最大乘积。
        return dp[n];
    }
}